归并排序

定义

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

动态演示

参考代码

arr = [5,8,3,9,10,490,90,50,40]

def merge(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    left = merge(arr[:mid])
    right = merge(arr[mid:])
    result = []
    i,j=0,0
    while True:
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
            if i == len(left):
                result += right[j:]
                break
        else:
            result.append(right[j])
            j += 1
            if j == len(right):
                result += left[i:]
                break
    return result

result = merge(arr)
print(result)